import java.util.*;
public class test {
    //leetcode 526.优美的排序
    class Solution {
        public int sum = 0;
        public int len;
        public boolean[] count;

        public int countArrangement(int n) {
            count = new boolean[n + 1];
            len = n;
            dfs(1);
            return sum;
        }

        public void dfs(int index) {
            if (index == len + 1) {
                sum++;
                return;
            }
            for (int i = 1; i <= len; i++) {
                if (!count[i] && (index % i == 0 || i % index == 0)) {
                    count[i] = true;
                    dfs(index + 1);
                    count[i] = false;
                }
            }
        }
    }
    //leetcode 51.N皇后
    class Solution {
        public List<List<String>> list;
        public List<String> path;
        public boolean[] col;
        public boolean[] count1;
        public boolean[] count2;
        public int n;
        public List<List<String>> solveNQueens(int n) {
            list = new ArrayList<>();
            path = new ArrayList<>();
            col = new boolean[n];
            count1 = new boolean[n * 2];
            count2 = new boolean[n * 2];
            this.n = n;
            //传参为行
            dfs(0);
            return list;
        }
        public void dfs(int row){
            if(row == n){
                list.add(new ArrayList<>(path));
                return;
            }
            char[] line = new char[n];
            Arrays.fill(line,'.');
            for(int c = 0;c < n;c++){
                int b1 = row - c + n;
                int b2 = row + c;
                if(!col[c] && !count1[b1] && !count2[b2]){
                    line[c] = 'Q';
                    path.add(new String(line));
                    col[c] = true;
                    count1[b1] = true;
                    count2[b2] = true;
                    dfs(row + 1);
                    line[c] = '.';
                    path.remove(path.size() - 1);
                    col[c] = false;
                    count1[b1] = false;
                    count2[b2] = false;
                }
            }
        }
    }
    //leetcode 52.N皇后Ⅱ
    class Solution {
        public int totalNQueens(int n) {
            int[] arr = new int[]{1,0,0,2,10,4,40,92,352};
            return arr[n - 1];
        }
    }
    //(这谁能忍住不打表?)
}
